package subject_set.lc200;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author haomin
 * @date 2023/03/26 21:49
 **/
public class Num207 {
    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            // 入度
            int[] inDegree = new int[numCourses];
            // 邻接表
            List<List<Integer>> adjacency = new LinkedList<>();
            Deque<Integer> q = new LinkedList<>();

            for(int i = 0; i < numCourses; ++i)
                adjacency.add(new LinkedList<>());
            for(int[] arr : prerequisites) {
                inDegree[arr[0]]++;
                adjacency.get(arr[1]).add(arr[0]);
            }
            for(int i = 0; i < numCourses; ++i) {
                // add 的是i
                if(inDegree[i] == 0) q.add(i);
            }

            while(!q.isEmpty()) {
                int pre = q.poll();
                numCourses--;
                for(int cur : adjacency.get(pre)) {
                    if(--inDegree[cur] == 0) q.offer(cur);
                }
            }
            return numCourses == 0;
        }
    }
}